#!/usr/bin/env python3
#-*- coding:utf-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2018年12月02日
描    述：
'''

class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tmp = []
        size = 0
        for num in nums:
            i = 0
            j = size
            while i < j:
                m = (j - i)//2 + i
                if tmp[m] < num:
                    i = m + 1
                else:
                    j = m
            if i == size:
                tmp.append(num)
                size = size + 1
            else:
                tmp[i] = num

        return size


